#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution {
public:
    void merge(vector<int>& A, int m, vector<int>& B, int n) {
        int la = m - 1, lb = n - 1, i = m + n - 1;
        while (la >= 0 && lb >= 0) {
            if (A[la] > B[lb]) A[i--] = A[la--];
            else A[i--] = B[lb--];
        }
        while (lb >= 0) A[i--] = B[lb--];
    }
};

class Solution {
    vector<string> ret;
    string path;
    bool check[9];
    int n;

public:
    void dfs(string& S) {
        if (path.size() == n) ret.push_back(path);
        for (int i = 0; i < n; i++) {
            if (check[i] == true || (i > 0 && S[i] == S[i - 1] && check[i - 1] == false)) continue;

            path += S[i];
            check[i] = true;
            dfs(S);
            path.pop_back();
            check[i] = false;
        }
    }
    vector<string> permutation(string S) {
        sort(S.begin(), S.end());
        n = S.size();
        dfs(S);
        return ret;
    }
};